#include "EventHash.h"

#include "EventString.h"

#include <libintl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _(String) gettext(String)

struct _HashItem
{
	struct _HashItem *next;
	//
	epointer key;
	epointer value;
	void	 (*destory)(epointer);
	bool	 is_delete_node;
};

static void
item_set_key(HashItem_p item, epointer key, EventHashModel model)
{
	if (model == EVENT_HASH_MODEL_CHARSET) {
		item->key = malloc(strlen((char *)key) + 1);
		strcpy((char *)item->key, (char *)key);
	} else if (model == EVENT_HASH_MODEL_STRING) {
		item->key = key;
		event_object_addref(key);
	} else {
		item->key = key;
	}
}

static HashItem_p
hash_item_create(epointer key, epointer value, void (*destory)(epointer),
		 EventHashModel model)
{
	HashItem_p item = MALLOC_NEW(struct _HashItem);

	item_set_key(item, key, model);
	item->value   = value;
	item->destory = destory;
	item->next    = NULL;
	//
	item->is_delete_node = false;

	return item;
}

static void
hash_item_remove(HashItem_p item, EventHashModel model)
{
	if (!item)
		return;
	if (item->is_delete_node)
		goto free_and_exit;
	if (item->destory)
		item->destory(item->value);
	if (model == EVENT_HASH_MODEL_STRING)
		event_object_unref(item->key);
	else if (model == EVENT_HASH_MODEL_CHARSET)
		free(item->key);
free_and_exit:
	free(item);
}

static void
hash_item_destory_chain(HashItem_p item, EventHashModel model)
{
	if (!item)
		return;
	hash_item_destory_chain(item->next, model);
	hash_item_remove(item, model);
}

struct _EventHash
{
	EventObject    parent_instance;
	HashItem_p    *table;
	HashItem_p    *cache;
	EventHashModel model;
	euint32	       used_size;
	euint32	       table_size;
	euint32	       table_size_old;
	euint32	       multi_size;
	euint32	       h_set;
	HashItem_p    *iter_node;
};

static void
event_hash_finalize(EventHash *self)
{
	if (self->table)
		for (int i = 0; i < self->table_size; ++i)
			hash_item_destory_chain(self->table[i], self->model);
	free(self->table);
}

EventHash *
event_hash_new(EventHashModel model)
{
	EventHash *object;

	object = MALLOC_NEW(EventHash);

	event_object_init(EVENT_OBJECT(object));
	event_object_set_finalize(object, FINALIZE(event_hash_finalize));

	object->table_size     = 0;
	object->table_size_old = 0;
	object->used_size      = 0;
	object->multi_size     = 8;
	object->model	       = model;
	object->table	       = NULL;
	object->cache	       = NULL;
	object->h_set	       = 0;
	object->iter_node      = NULL;

	return object;
}

static euint32
event_hash(epointer key, EventHashModel model, euint32 table_size)
{
	euint32	    sum	 = 0;
	euint64	    _key = (euint64)key;
	const char *cptr = NULL;

	switch (model) {
	case EVENT_HASH_MODEL_NUMBER:
		do {
			sum += 17 * _key;
			_key = (_key - _key % 17) / 17;
		} while (_key > 17);
		goto return_hash_code;
	case EVENT_HASH_MODEL_STRING:
		if (!key) {
			cptr = NULL;
			break;
		}
		cptr = event_string_get_string(EVENT_STRING(key));
		break;
	case EVENT_HASH_MODEL_CHARSET:
		cptr = (char *)key;
		break;
	default:
		return 0;
	}

	return_val_if_fail(cptr != NULL, self, 0);

	sum = 5831;
	while (*cptr != '\0') {
		sum   = (sum << 5) + sum + (euint32)(*cptr) + 17;
		cptr += 1;
	}

return_hash_code:
	return sum % table_size;
}

/**
 * 内存爆炸存档点：任何时候都要谨慎判断内存。
 *
 * 爆炸原因：大于 0.8 或小于 0.1 无额外判断就返回 true；
 * 导致判断是否需要重哈希时，因起始比率过小，直接返回 true，
 * 导致无限倍增，内存爆炸，系统锁死
 */
static bool
need_rehash(EventHash *self, bool is_shrink)
{
	double rate = (double)self->used_size / (double)self->table_size;

	if (is_shrink && rate < 0.15)
		return true;
	else if (!is_shrink && rate > 0.8)
		return true;
	return false;
}

static void
rehash(EventHash *self)
{
	HashItem_p node, next = NULL, *slot;
	euint32	   h_set_old = 0, h_set;

retry:
	node = self->table[h_set_old];
	if (!node)
		goto add_and_retry;
	while (node) {
		if (node)
			next = node->next;
		if (node->is_delete_node) {
			free(node);
			node = next;
			continue;
		}
		h_set = event_hash(node->key, self->model, self->table_size);
		slot  = &self->cache[h_set];
		while (*slot)
			slot = &(*slot)->next;
		(*slot)	   = node;
		node->next = NULL;
		node	   = next;
	}
add_and_retry:
	h_set_old += 1;
	if (h_set_old < self->table_size_old)
		goto retry;

	free(self->table);
	self->table = self->cache;
}

static void
hash_add_table_size(EventHash *self)
{
	if (self->table_size == 0) {
		self->table_size = self->multi_size;
		self->table	 = (HashItem_p *)malloc((self->table_size) *
							sizeof(HashItem_p));
		for (euint32 i = 0; i < self->table_size; ++i)
			self->table[i] = NULL;
		return;
	}
	self->table_size_old = self->table_size;
	self->table_size    *= 2;
	self->cache =
		(HashItem_p *)malloc((self->table_size) * sizeof(HashItem_p));
	for (euint32 i = 0; i < self->table_size; ++i)
		self->cache[i] = NULL;
	rehash(self);
}

static void
hash_reduce_table_size(EventHash *self)
{
	if (self->table_size <= self->multi_size)
		return;
	self->table_size_old = self->table_size;
	self->table_size    /= 2;
	self->cache =
		(HashItem_p *)malloc((self->table_size) * sizeof(HashItem_p));
	for (euint32 i = 0; i < self->table_size; ++i)
		self->cache[i] = NULL;
	rehash(self);
}

/**
 * 比较键值是否一样
 */
static bool
compare_key(epointer key1, epointer key2, EventHashModel model)
{
	switch (model) {
	case EVENT_HASH_MODEL_NUMBER:
		return (key1 == key2);
	case EVENT_HASH_MODEL_CHARSET:
		return (strcmp((char *)key1, (char *)key2) == 0);
	case EVENT_HASH_MODEL_STRING:
		return event_string_compare(EVENT_STRING(key1),
					    EVENT_STRING(key2));
	}
	return false;
}

static HashItem_p *
get_slot(EventHash *self, epointer key)
{
	HashItem_p *slot;
	euint32	    h_set;
	bool	    is_founded = false;

	if (!self->table)
		return NULL;

	h_set = event_hash(key, self->model, self->table_size);
	slot  = &self->table[h_set];

	while (*slot != NULL) {
		if (!(*slot)->is_delete_node &&
		    compare_key((*slot)->key, key, self->model)) {
			is_founded = true;
			break;
		}
		slot = &(*slot)->next;
	}
	return is_founded ? slot : NULL;
}

epointer
event_hash_get(EventHash *self, epointer key)
{
	HashItem_p *slot;

	return_val_if_fail(self != NULL, event_hash_get, NULL);
	if (self->model != EVENT_HASH_MODEL_NUMBER)
		return_val_if_fail(key != NULL, event_hash_get, NULL);

	slot = get_slot(self, key);
	return slot ? (*slot)->value : NULL;
}

void
event_hash_set(EventHash *self, epointer key, epointer value,
	       void (*destory)(epointer))
{
	HashItem_p *slot;
	euint32	    h_set;

	return_if_fail(self != NULL, event_hash_set);
	if (self->model != EVENT_HASH_MODEL_NUMBER)
		return_if_fail(key != NULL, event_hash_set);

	if (self->table_size != 0 && (slot = get_slot(self, key))) {
		/* 预防意外 bug：不会销毁同一个对象 */
		if ((*slot)->value != value && (*slot)->destory)
			(*slot)->destory((*slot)->value);
		(*slot)->value	 = value;
		(*slot)->destory = destory;
		return;
	} else if (self->table_size == 0) {
		hash_add_table_size(self);
	}

	h_set = event_hash(key, self->model, self->table_size);
	slot  = &self->table[h_set];

	while (*slot != NULL) {
		if ((*slot)->is_delete_node)
			break;
		slot = &(*slot)->next;
	}

	if (*slot == NULL) {
		*slot = hash_item_create(key, value, destory, self->model);
	} else {
		item_set_key(*slot, key, self->model);
		(*slot)->value		= value;
		(*slot)->destory	= destory;
		(*slot)->is_delete_node = false;
	}
	self->used_size += 1;

	if (need_rehash(self, false))
		hash_add_table_size(self);
}

void
event_hash_remove(EventHash *self, epointer key)
{
	HashItem_p *slot;

	return_if_fail(self != NULL, event_hash_remove);
	if (self->model != EVENT_HASH_MODEL_NUMBER)
		return_if_fail(key != NULL, event_hash_remove);

	slot = get_slot(self, key);

	if (!slot)
		return;
	if ((*slot)->destory)
		(*slot)->destory((*slot)->value);
	if (self->model == EVENT_HASH_MODEL_CHARSET)
		free((*slot)->key);
	else if (self->model == EVENT_HASH_MODEL_STRING)
		event_object_unref((*slot)->key);
	(*slot)->is_delete_node = true;
	self->used_size	       -= 1;

	if (need_rehash(self, true))
		hash_reduce_table_size(self);
}

bool
event_hash_verify_exist(EventHash *self, epointer key)
{
	return_val_if_fail(self != NULL, event_hash_verify_exist, false);
	return get_slot(self, key) != NULL;
}

void
event_hash_set_multi_size(EventHash *self, euint32 multi_size)
{
	return_if_fail(self != NULL, event_hash_set_multi_size);
	self->multi_size = (multi_size > 6) ? multi_size : 6;
}

static eint32 *
statistics_allocation(HashItem_p *table, euint32 t_size)
{
	HashItem_p   *slot;
	static eint32 status[100][2], sta_slot = 0;
	for (int i = 0; i < 100; ++i) {
		status[i][0] = -1;
		status[i][1] = 0;
	}
	for (euint32 i = 0; i < t_size; ++i) {
		euint32 count = 0;
		sta_slot      = 0;
		slot	      = &table[i];
		while (*slot) {
			if (!(*slot)->is_delete_node)
				count += 1;
			slot = &(*slot)->next;
		}
		for (int j = 0; j < 100; ++j, ++sta_slot)
			if (status[j][0] == -1 || status[j][0] == count)
				break;
		if (sta_slot >= 100) {
			printf("Warning: Statistics slot is full!\n");
			break;
		}
		if (status[sta_slot][0] == -1) {
			status[sta_slot][0]  = count;
			status[sta_slot][1] += 1;
		} else if (status[sta_slot][0] == count) {
			status[sta_slot][1] += 1;
		}
	}
	/* 对统计槽进行排序 */
	bool   flag = true;
	eint32 tmp;
	while (flag) {
		flag = false;
		for (int i = 0; i < 100 - 1; ++i) {
			if (status[i + 1][0] == -1)
				break;
			if (status[i][0] > status[i + 1][0]) {
				tmp		 = status[i][0];
				status[i][0]	 = status[i + 1][0];
				status[i + 1][0] = tmp;
				tmp		 = status[i][1];
				status[i][1]	 = status[i + 1][1];
				status[i + 1][1] = tmp;
				flag		 = true;
			}
		}
	}
	return &status[0][0];
}

void
event_hash_print_status(EventHash *self)
{
	eint32 *status;
	return_if_fail(self != NULL, event_hash_print_status);

	printf("\n=================================================\n");
	printf(_("Basic information:\n"));
	printf(_("\tEventHash component, address: %p\n"), self);
	printf(_("\tKey mode: "));
	switch (self->model) {
	case EVENT_HASH_MODEL_NUMBER:
		printf(_("Integer mode\n"));
		break;
	case EVENT_HASH_MODEL_CHARSET:
		printf(_("Normal string mode\n"));
		break;
	case EVENT_HASH_MODEL_STRING:
		printf(_("EventString object mode\n"));
		break;
	default:
		printf(_("Unknown mode\n"));
		break;
	}
	printf(_("\tMultiple increment: %u\n"), self->multi_size);
	printf(_("\tUsage: %.02lf %% (used %u / total %u)\n"),
	       100 * (double)((double)self->used_size /
			      (double)self->table_size),
	       self->used_size, self->table_size);
	printf(_("Iteration situation:\n"));
	printf(_("\tTotal number of slots: %u\n"), self->table_size);
	printf(_("\tCurrent iteration slot number: %u\n"), self->h_set);
	printf(_("\tCurrent iteration object: %p\n"),
	       self->iter_node ? *(self->iter_node) : NULL);
	printf(_("Allocation situation:\n"));
	euint32 used = 0;
	if (self->table) {
		status = statistics_allocation(self->table, self->table_size);
		for (int i = 0; i < 100; ++i) {
			if (*status == -1)
				break;
			printf(_("\tNumber of slots with %d elements: %d\n"),
			       *(status), *(status + 1));
			if (*status != 0)
				used += *(status + 1);
			status += 2;
		}
		printf(_("Hash slot utilization rate: %.2lf %%\n"),
		       100.0 * ((double)used / (double)self->used_size));
	} else {
		printf(_("\tTable space not yet allocated\n"));
	}
	printf("=================================================\n");
}

void
event_hash_iter_reset(EventHash *self)
{
	return_if_fail(self != NULL, event_hash_iter_reset);

	self->h_set	= 0;
	self->iter_node = NULL;
}

HashItem_p
event_hash_iter_get(EventHash *self)
{
	HashItem_p item;
	return_val_if_fail(self != NULL, event_hash_iter_get, NULL);

	if (!self->table)
		return NULL;
	if (self->h_set >= self->table_size)
		return NULL;
	if (self->h_set == 0 && self->iter_node == NULL)
		self->iter_node = &self->table[0];

	for (euint32 i = self->h_set; i < self->table_size; ++i) {
		if (*(self->iter_node) == NULL) {
			self->h_set += 1;
			if (self->h_set >= self->table_size)
				return NULL;
			self->iter_node = &self->table[self->h_set];
		} else {
			while (*(self->iter_node)) {
				if (!(*(self->iter_node))->is_delete_node)
					goto detected;
				*(self->iter_node) = (*(self->iter_node))->next;
			}
		}
	}
	return NULL;
detected:
	item		= *(self->iter_node);
	self->iter_node = &(*(self->iter_node))->next;
	return item;
}

epointer
event_hash_item_get_key(HashItem_p item)
{
	return_val_if_fail(item != NULL, event_hash_item_get_key, NULL);
	return item->key;
}

epointer
event_hash_item_get_value(HashItem_p item)
{
	return_val_if_fail(item != NULL, event_hash_item_get_value, NULL);
	return item->value;
}

void (*event_hash_item_get_destory(HashItem_p item))(epointer)
{
	return_val_if_fail(item != NULL, event_hash_item_get_destory, NULL);
	return item->destory;
}

euint32
event_hash_get_used_size(EventHash *self)
{
	return_val_if_fail(self != NULL, event_hash_get_used_size, 0);
	return self->used_size;
}
